package lc;
import org.junit.*;
import java.util.*;
import java.util.concurrent.atomic.AtomicBoolean;
public class Ex560 {
    class Solution1 {
        public int subarraySum(int[] nums, int k) {
            int cnt = 0, n = nums.length;
            int lo = 0, hi = 0, cur = 0;
            while (hi < n) {
                while (hi < n && cur < k) {
                    cur += nums[hi++];
                }
                if (cur < k) {
                    break;
                }
                while (lo < hi) {
                    if (k + nums[lo] <= cur) {
                        cur -= nums[lo++];
                    } else {
                        break;
                    }
                }
                if (cur == k) {
                    cnt++;
                }
    
                if (lo == n) {
                    break;
                }
                //移动左指针，进入下一轮求解
                cur -= nums[lo++];
            }
    
            return cnt;
        }
    }

    class Solution {
        public int subarraySum(int[] nums, int k) {
            int cnt = 0, n = nums.length, sum = 0;
            Map<Integer, Integer> map = new HashMap<>();
            // map.put(0, 1); //没有也是0
            for (int i = 0; i < n; i++) {
                sum += nums[i];
                map.put(sum, map.getOrDefault(sum, 0) + 1);
                int tar = k-sum;
                if (map.containsKey(tar)) {
                    cnt += map.get(tar);
                }
            }
            System.out.println(map);
            return cnt;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{1,-1,0};
        System.out.println(s.subarraySum(nums, 0));
        
    }
}
